package 中等.栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
 * 由于答案可能很大，因此 返回答案模 10^9 + 7 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sum-of-subarray-minimums
 */
public class 子数组的最小值之和_907 {

    public static void main(String[] args) {

        System.out.println(sumSubarrayMins2(new int[]{3, 1, 2, 4}));

    }

    /**
     * 模拟（超时）
     * 将以 arr[i] 结尾的子数组最小值累加
     *
     * @param arr
     * @return
     */
    public static int sumSubarrayMins(int[] arr) {
        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            int curMin = Integer.MAX_VALUE;
            for (int j = i; j >= 0; j--) {
                curMin = Math.min(curMin, arr[j]);
                sum += curMin;
                if (sum > 1000000007) {
                    sum -= 1000000007;
                }
            }
        }

        return sum;
    }

    /**
     * 单调栈
     * 索引相对顺序为，[1 a ... i 2 ... b]，如果对于 (a,i] ，arr[i]是以 arr[i] 结尾
     * 的所有子数组的最小值，arr[a] 的位置是小于等于 arr[i] 的左边第一个数，此时有 (i-a)
     * 个子数组的最小值为 arr[i]
     * 相对的，arr[b] 的位置也是小于等于 arr[i] 右边的第一个数，此时有 (b-i) 个子数组的
     * 最小值的最小值为 arr[i]
     * 那么对于 arr[i] 对于答案的贡献值为
     * 注意：
     * 1，可能存在 arr[i] == arr[b] 的情况，此时会重复计算子数组，重新定义 arr[b]
     * 所在的位置，为小于 arr[i] 的右边第一个数，一开一闭区间
     * 2，找 a 和 b 的位置可以用单调栈
     * 3，arr[i] 的定义是以 arr[i] 为最小值的子数组数量，贡献值计算
     * (i-a)*(b-i)*arr[i]，左边的数量乘以右边的数量
     *
     * @param arr
     * @return
     */
    public static int sumSubarrayMins2(int[] arr) {
        int sum = 0;
        int[] arrA = new int[arr.length];
        int[] arrB = new int[arr.length];

        // 需要存索引，才能计算相对位置距离
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peekFirst()] > arr[i]) {
                stack.pollFirst();
            }
            arrA[i] = stack.isEmpty() ? -1 : stack.peekFirst();

            stack.addFirst(i);
        }
        stack.clear();
        for (int i = arr.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peekFirst()] >= arr[i]) {
                stack.pollFirst();
            }
            arrB[i] = stack.isEmpty() ? arr.length : stack.peekFirst();

            stack.addFirst(i);
        }

        for (int i = 0; i < arrA.length; i++) {
            sum += (i - arrA[i]) * 1L * (arrB[i] - i) % 1000000007 * arr[i] % 1000000007;
            if (sum > 1000000007) {
                sum -= 1000000007;
            }
        }

        return sum;
    }

}
